package org.lql.algo.codecrush.hot100.stack;

import org.w3c.dom.css.Rect;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author: liangqinglong
 * @date: 2025-10-14 21:43
 * @description: 84. 柱状图中最大的矩形 <a href="https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class LargestRectangleArea {

	public int largestRectangleArea(int[] heights) {
		if (heights == null || heights.length == 0) {
			return 0;
		}
		int n = heights.length;
		int[] newHeights = new int[n + 2]; // 加左右哨兵
		System.arraycopy(heights, 0, newHeights, 1, n);
		heights = newHeights;
		int ans = 0;
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < heights.length; i++) {
			while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
				int height = heights[stack.pop()];
				int width = i - stack.peek() - 1;
				ans = Math.max(ans, height * width);
			}
			stack.push(i);
		}
		return ans;
	}

	static class React {
		int width;
		int height;

		public React(int width, int height) {
			this.width = width;
			this.height = height;
		}
	}

	public int largestRectangleAreaReact(int[] heights) {
		int n = heights.length;
		heights = Arrays.copyOf(heights, n + 1);
		Stack<React> stack = new Stack<>();
		int ans = 0;
		for (int height : heights) {
			int accWidth = 0;
			while (!stack.isEmpty() && stack.peek().height > height) {
				React react = stack.pop();
				accWidth += react.width;
				ans = Math.max(ans, accWidth * react.height);
			}
			stack.push(new React(accWidth + 1, height));
		}
		return ans;
	}


	public static void main(String[] args) {
		LargestRectangleArea largestRectangleArea = new LargestRectangleArea();
		System.out.println(largestRectangleArea.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
		System.out.println(largestRectangleArea.largestRectangleArea(new int[]{2, 4}));
		System.out.println(largestRectangleArea.largestRectangleAreaReact(new int[]{2, 1, 5, 6, 2, 3}));
		System.out.println(largestRectangleArea.largestRectangleAreaReact(new int[]{2, 4}));
	}
}
